// 时间复杂度: 平均O(nlog2n) 最坏O(n2) 最好O(nlog2n)
// 空间复杂度: O(log2n) 或 O(n)
// 稳定性: 不稳定排序

class QuickSort {
private:
    static int quickArray(int *array, int left, int right) {
        int i = left;
        int j = right;
        int base = array[left];

        while (i < j) {
            while (i < j && base <= array[j]) j--;
            array[i] = array[j];

            while (i < j && array[i] < base) i++;
            array[j] = array[i];
        }

        array[i] = base;
        return i;
    }

public:
    static void quickSort(int *array, int left, int right) {
        if (right <= left) {
            return;
        }

        int index = quickArray(array, left, right);

        quickSort(array, left, index - 1);
        quickSort(array, index + 1, right);
    }
};
